1. Field of the Invention.
This invention relates in general to computer aided design (CAD) systems, and more particularly, to a method, apparatus and article of manufacture for performing spatial index compression through spatial subdivision encoding.
2. Description of Related Art.
Spatial indices are useful in graphical applications such as computer-assisted drafting (CAD), where data has spatial extents and often the user is working with a subset of data defined by a spatial subset of the database extents. In typical CAD applications, the database is saved in a binary file. Since projects are organized and information exchanged through these files, it is beneficial to store data in a compressed form in such a way that access and decoding of the data is efficient as well.
Numerous structures have been proposed to represent spatial data, including an oct-tree and an R-tree, as described in Hanan Samet, xe2x80x9cThe Design and Analysis of Spatial Data Structures,xe2x80x9d Addison-Wesley, 1990, which is incorporated by reference herein.
Although the oct-tree structure has the benefit of simplicity, there are limitations to the oct-tree:
Objects that lie on partitioning planes end up near the root, even if they are of small extents.
The oct-tree does not handle data that degenerates along a dimension. For example, if the data set consists of buildings of all the same height (Z extent), they will all end up being classified at the root. The oct-tree lacks the ability to adapt to such a situation. A quad-tree would be an appropriate structure for this case.
The R-Tree is object-extent-based, as opposed to global-extent-subdivision-based, as described in A. Guttman, xe2x80x9cR-Trees: A Dynamic Index Structure for Spatial Searching,xe2x80x9d Proceedings of the Annual Meeting ACM SIGMOD, Boston, Mass., 1984, which is incorporated by reference herein.
Although the R-Tree has the advantage of generality, there are also limitations to the R-tree:
Input data distribution can skew the R-tree and make it degenerate fairly easily. For example, if the first object added to the tree spans the database extents, then adding subsequent objects will force the node containing the first large) object to migrate to a greater depth. So the tree will essentially become linear. This sensitivity to input data distribution makes it necessary to introduce additional heuristics in tree creation in order to control degeneracies.
The present invention describes a restricted version of the R-tree that enhances the oct-tree to solve specific limitations of the oct-tree. The present invention solves some oct-tree limitations without permitting the degeneracies possible in the general R-tree. For convenience of notation, this structure is called a Cell tree, where each node in the tree is known as a Cell. A pointer-less representation is used for making the structure persistent.
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus and article of manufacture for reducing the total storage used in representing data having spatial extents. The data is represented in a tree structure having a plurality of nodes, wherein each of the nodes has parent and child relationship to one or more others of the nodes in the tree structure. An encoded representation of the relation of a child node""s extents with respect to its parent is stored in the node. A preorder traversal of the tree structure is performed to store it compactly in an output file.